Print Branch A: .11
V: w

11 CHESS<PBS>
   11A FOURTH UNITED STATES COMPUTER CHESS CHAMPIONSHIP
   from
   ACM-73 NEWS RELEASE
      11A1 A record field of between twelve and sixteen teams will
      participate in the Fourth United States Computer Chess
      Championship.  The tournament will be held as a Special Event at
      the ACM's Annual Conference in Atlanta, Georgia.  The first two
      rounds of play will be held on Sunday, August 26, the third round
      on the evening of August 27, and the final round on the evening
      of August 28.
      11A2 Returning to defend their title is the team of Larry Atkin,
      Keith Gorlen, and David Slate.  Their program has won the
      previous three tournaments without the loss of a game.  Their
      program, called Chess 4.0, uses a CDC 6400 on the Northwestern
      University campus.  Also entered are programs written by Jim
      Gillogly (PDP-10), George Arnold and Monty Newborn (Data General
      Supernova), Dennis Cooper and Ed Kozdrowicki (UNIVAC 1108), Ken
      Thompson (PDP-11/45), and Al Zobrist, Fred Carlson, and Charles
      Kalme (IBM 370/155).  Many of the programs were developed at
      America's leading universities; included are Georgia Tech., MIT,
      Carnegie-Mellon, USC, U. Cal-Berkeley, Dartmouth, Texas A&M, and
      Columbia.
      11A3 David Levy, an international Chess Master from England, will
      serve as tournament director.  A panel discussion, moderated by
      Ben Mittman, is also scheduled during the ACM's conference.  The
      tournament is being sponsored in part by Control Data
      Corporation, International Business Machine Corporation,
      Sperry-UNIVAC, and National Data Industries. <PES>
      11A4 Tournament Participants <PES>
   11B RESEARCH PROGRESS REPORT IN COMPUTER CHESS* <LBS=1><GCR>by
   <GCR>Richard J. Cichelli
   901 Whittier Drive
   Allentown, Pennsylvania 18103
      11B1 This working paper describes a developing brute-force
      middle-game chess program.  New concepts are clarified and
      comparisons with existing programs are made.  The mechanisms
      described are sufficient to enable information collected during
      search to be used for dynamic search ordering and dynamic forward
      pruning.  The suggested mechanisms replace the static plausible
      move generators in existing programs.
      11B2 Background
         11B2A Brute force chess programs are characterized by their
         large game tree searches and simple evaluation functions.  In
         addition, little of their computational time is spent in
         computations involving chess specific knowledge.  James
         Gillogly's TECH [1] is an example of such a program.  TECH
         searches as many as 500,000 end nodes, uses only material for
         evaluation, and spends less than 5% of its time applying chess
         specific knowledge.
         11B2B More sophisticated programs such as CHESS 3.6 (the
         currently reigning world champion) and the Greenblatt program
         manage to search effectively by using highly developed
         plausible move generators.  These routines embody much of the
         chess program's chess knowledge; at each depth, at move
         listing time, they order and forward prune the legal move
         list.  A good ordering increases the probability of alpha-beta
         cutoffs; forward pruning further limits the game tree size and
         hopefully keeps it manageable while still including the
         analysis tree (i.e., the tree a Grandmaster would search in
         the same position).  The Zobrist [2], CHESS 3.6 (Slate) [3],
         and Greenblatt [4] programs have game trees with fewer than
         20,000 end nodes.
         11B2C Dr. Zobrist's program is an attempt to produce the
         ultimate plausible move generator by giving much chess
         knowledge to the program.  Alternatively, my approach is to
         gather information during search and to use this
         position-specific data to guide further search.
         11B2D --------------------------------
         11B2E *[Ed. Note:  Mr. Cichelli has indicated that he welcomes
         responses (questions, rebuttals, etc.) on this paper from
         interested readers.
      11B3 Overview <PBS>
         11B3A The brute force chess program I am currently developing
         uses two types of information to order searchable plies and to
         forward prune.  Refutation data is global to the tree and
         DEPTH-minus-two data is local to move pairs (1 move = two
         plies).
      11B4 Refutation Data
         11B4A Given a ply "A" such that making "A" leads to a
         non-terminal position, then some ply "B" is the best reply to
         "A".  In short, B refutes A.  Should a ply A' which is similar
         to A (i.e., same piece, same square-to) be made subsequently
         in the game tree then should B' exist, it will probably be a
         good ply to try first.  To implement this and its logical
         extension, best (and possibly, second best) refuters against
         moving the piece of A and moving to the square-to of A, simply
         requires an array indexed by side, piece, and square-to
         containing the refutation piece, square-to, and its value
         (i.e., the backup value B got when refuting A).
         11B4B Refutation data is continuously updated with superior
         refuters encountered during search.  Since A - B pairs are not
         considered in the context of a particular game tree node but
         span the entire search tree, refutation data collection is
         said to be global to the tree.
      11B5 DEPTH-Minus-Two Data
         11B5A If one visualizes a depth first game tree being grown
         down and from the left, then backup values pass up and to the
         right.  Thus, for nodes at depths greater than three, there
         are plies in lists at DEPTH-2 which are similar (i.e., same
         piece and square-to) to plies at the current DEPTH.  Each ply
         at the current DEPTH will lead to a node which will receive a
         backup value and will probably receive this value before the
         node for the similar ply at DEPTH-2 is reached and evaluated. 
         Plies which do well at DEPTH+2 should be searched earlier at
         DEPTH, and those which do poorly at DEPTH+2 may not need to be
         searched at all at DEPTH.  Significantly, previously
         accumulated DEPTH-2 data can be used in a preliminary ordering
         of plies at DEPTH.  The following diagrams illustrate the two
         types of game tree information gathering. <PEL><BM=62><GCR=28>
         11B5B To implement this DEPTH-minus-two heuristic, the program
         needs to maintain, at each depth, a list of plies with storage
         with each ply for three backup value data elements (a total,
         count, and average).  After listing the plies at DEPTH, a
         seaach of the DEPTH-2 plies is made and back pointers are set
         for similar plies.  Preordering can be accomplished by setting
         initial counts of 1 and setting the total and average equal to
         the previous average at DEPTH-2.*
         11B5C By listing the opponent's moves at DEPTH 0 and making
         "no move", the program can provide storage for DEPTH-2 values
         for DEPTH=2.  Searching the ply lists is speeded by listing
         plies, by piece, in the same order at each move, as
         implemented in Bell's algorithm [5].
         11B5D --------------------------------
         *After the initialization of move values with DEPTH-2 data,
         refutation ordering data can be applied to those refuters of
         the previous move by adding N times the refutation value to
         the total, increasing the count by N, and calculating the new
         average.  (I have used the values 3,2,1,2,1 for N when
         applying refutation values to the best refuter, best and
         second best against moved piece, and best and second best
         against moved square-to).
      11B6 Forward Pruning<PBS><BM=58>
         11B6A Since one can expect more than 80% of the plies at any
         two successive moves to be the same, plies at DEPTH will have
         counts about <GCR=5>
         11B6B With a width of 7, one would expect a count of nearly
         300.  The contention here is that the average, generated for
         high counts, approaches the backup value of that ply's
         successor node, i.e., predicts the backup value.
         11B6C Within this information framework a ply selector would
         function by referencing the ply list at current DEPTH and
         picking the best unsearched ply (by its average) and passing
         it to the MAKEMOVE routine if there existed some ply in the
         ply list whose count was below the threshold for the current
         DEPTH and/or whose average was not worse by some factor than
         the DEPTH's current alpha-beta value.  Note:  a feedback
         mechanism is hereby created, for heavy pruning at some DEPTH
         will result in lower counts at predecessor DEPTHs and thus
         broaden search at predecessor levels.
         11B6D I am experimenting with broad, shallow searches (3 ply
         to capture-promote-check quiessence) to initialize the
         refutation and ply 0 and 1 values followed by a much deeper,
         narrower search.  The evaluation function is material (Pawn =
         100) and mobility (1 for each legal ply).
      11B7 Implementation
         11B7A My program is approximately 1500 short lines of PASCAL
         code [6] and performs nearly all of the functions described
         above.  It also includes an extensive user interface.  So far,
         it has been a part-time four week effort and will probably be
         ready for actual games in two more weeks.  Batteries of
         searching strategies are being compared; this is easily
         accomplished because the SELECTMOVE routines are parameters to
         the SEARCH routine. 
         11B7B With the PASCAL assignment checking feature negated and
         ply records packed for optimal use of storage, the program
         [including the 5K (octal) PASCAL operating system] will
         probably run in less than 25K (octal) 60 bit words on the CDC
         6400.
      11B8 Conclusion<PBS><LBS=2>
         11B8A The mechanisms described here present methods for using
         information gathered during search to dynamically order and
         prune plies in a depth-first game tree.  Though the example
         problem space is chess, the concepts and methods are not in
         any way chess dependent.  I suspect, however, that the methods
         may not be applicable to games like GO (too large a potential
         search space) or Kalah (too large a change between plies).
      11B9 REFERENCES
         11B9A [1] Gillogly, James J., "The Technology Chess Program,"
         Carnegie-Mellon University, Department of Computer Science,
         1971.
         11B9B [2] Zobrist, Albert L. and Frederic R. Carlson, Jr., "An
         Advice-Taking Chess Computer," SCIENTIFIC AMERICAN, June, 1973
         11B9C [3] Slate, David J., Larry Atkin, and Keith Gorlen,
         CHESS 3.6, Vogelback Computing Center, Northwestern
         University.
         11B9D [4]Greenblatt, R.D., D. Eastlake, and S. Crocker, "The
         Greenblatt Chess Program," Proc. AFIPS 1967 FJCC.
         11B9E [5] Bell, A.G., "How to Program a Computer to Play Legal
         Chess," The Computer Journal, May, 1970.
         11B9F [6] Wirth, Niklaus, "The Programming Language Pascal
         (Revised Report)," University of Colorado Computing Center,
         1972.
   11C RECENT PAPERS ON CHESS<PBS>
      11C1 SKILL IN CHESS <GCR>by <GCR>Herbert A. Simon and William G.
      Chase
      Psychology Department, Carnegie-Mellon University
      Pittsburgh, Pennsylvania
      In AMERICAN SCIENTIST, Vol. 61, No. 4, pp. 394-403
      July-August 1973
         11C1A Experiments with chess-playing tasks and computer
         simulation of skilled performance throw light on some human
         perceptual and memory processes.
      11C2 COKO: THE COOPER-KOZ CHESS PROGRAM <GCR>by <GCR>Edward W.
      Kozdrowicki
      University of California at Davis
      and
      Dennis W. Cooper
      Bell Telephone Laboratories
      Whippany, New Jersey
      Communications of the ACM, Vol, 16, No. 7, pp. 411-427
      July 1973
         11C2A COKO III is a chess player written entirely in Fortran. 
         On the IBM 360-65, COKO III plays a minimal chess game at the
         rate of .2 sec cpu time per move, with a level close to lower
         chess club play.  A selective tree searching procedure
         controlled by tactical chess logistics allows a deployment of
         multiple minimal game calculations to achieve some optimal
         move selection.  The tree searching algorithms are the heart
         of COKO's effectiveness, yet they are conceptualy simple.  In
         addition, an interesting phenomenon called a tree searching
         catastrophe has plagued COKO's entire development just as it
         troubles a human player.  Standard exponential growth is
         curbed to a large extent by the definition and trimming of the
         Fischer set.  A clear distinction between tree pruning and
         selective tree searching is also made.  Representation of the
         chess environment is described along with a strategical
         preanalysis procedure that maps the Lasker regions.  Specific
         chess algorithms are described which could be used as a
         command structure by anyone desiring to do some chess program
         experimentation.  A comparison is made of some mysterious
         actions of human players and COKO III.

*